package leetcode;

//买卖股票最佳时机4
public class MaxProfit {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n < 2 || k == 0) {
            return 0;
        }
        int[] buy = new int[k];
        int[] sell = new int[k];
        for (int j = 0; j < k; j++) {
            buy[j] = -prices[0];//第j次买入 初始状态
            //sell[j] = 0;//第j次卖出 初始状态 int默认是0 可不需要
        }
        for (int i = 1; i < n; i++) {
            buy[0] = Math.max(buy[0], -prices[i]);
            sell[0] = Math.max(sell[0], buy[0] + prices[i]);
            for (int j = 1; j < k; j++) {
                buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]);//在第一次卖出的基础上哪天买入更省钱哪天买
                sell[j] = Math.max(sell[j], buy[j] + prices[i]); //第一次卖出与不卖出取收入最大的
            }
        }
        return sell[k - 1];
    }
}
